The present invention relates generally to computer graphics systems using applications such as line drawing, polygon edge computing, texture mapping, and image scaling. More particularly, the present invention relates to a digital differential analyzer using improved linear interpolation procedures for use in such computer graphics applications.
In a computer graphics system, it is desirable to represent an object as efficiently as possible to preserve memory and system bandwidth, and to enhance rendering speed. Computer graphics, such as in computer generated images, animations and effects for motion pictures, television, computer multi-media, computer games, print and other media, often employ applications such as line drawing, polygon edge computing, texture mapping, image scaling, and Gouraud shading during rendering images of three-dimensional (3D) objects. Linear interpolation is one of the fundamental procedures in computer graphics applications. Because linear interpolation is often used at the lowest level in a graphics driver, it is desirable to perform the linear interpolation as rapidly as possible.
A digital differential analyzer (DDA) is a mathematical function that is used to linearly interpolate and quantize a mathematical model, such as the rendering of a line or other computer graphics applications. However, conventional DDAs are computation intensive because they use comparisons or divisions.
One such DDA is described in Eker, Faster Linear Interpolation, Graphics Gems IV, Edited by Heckbert, Academic Press, Inc., (1994) pp. 526-533. Eker""s DDA requires the integer to be extracted from the result. This requirement is expensive in terms of processor time. Moreover, the DDA of Eker is restricted to linear interpolation directed to rounding with respect to the floor over a very small range.
There are a wide range of applications involving computer graphics in which it is necessary or desirable to provide efficient and accurate linear interpolation. Accordingly, the present invention provides an improved DDA that is efficient and accurate and avoids using comparisons.
This invention addresses the problem of providing improved (faster for a given amount of computer resources) linear interpolation procedures for use in computer graphics applications such as line drawing, computing polygon edges, texture mapping, and image scaling.
The present invention provides a digital differential analyzer (DDA) that avoids using comparisons that occur in the prior art DDAs, and instead uses shifts, multiplies, and adds. Shifts are less costly to use in terms of processor time, and already exist in the hardware of a computer graphics system. The present invention uses shifts to generate an xe2x80x9cimposterxe2x80x9d DDA having a larger denominator that substantially exactly simulates a DDA for a finite number of terms. The imposter DDA is a fixed point simulator of the original DDA that provides error-free approximations. Preferably, the imposter DDA is stored as a data structure in memory.
Other features of the invention are described below.